package figureAndGraph;

import lombok.Data;
import tree.heap.myDefinedGraphHeap.DefinedGraphHeap;
import utils.CollectionUtils;

import java.util.*;
import java.util.stream.Collectors;

public class MyGenerateGraph {
	@Data
	public static class Value {
		/**
		 * 权重
		 */
		public int weight;
		/**
		 * from节点
		 */
		public String from;
		/**
		 * to节点
		 */
		public String to;

		public Value(int weight, String from, String to) {
			this.weight = weight;
			this.from = from;
			this.to = to;
		}
	}

	public static void main(String[] args) {
		// 测试 DFS and BFS graph
//		testDFSAndBFSGraph();
		List<Value> valueList = generateRandomValue(10);
//		Graph graph = generateDirectedGraph(valueList).orElse(new Graph());
		Graph graph = generateNoDirectedGraph(valueList).orElse(new Graph());
		Node from = (Node) graph.nodeMap.get(valueList.get(0).from);
		Map<Node, Integer> nodeIntegerMap = dijkstra1(from);

		Map<Node, Integer> nodeIntegerMap1 = dijkstra2(from);
		System.out.println("test End");
//		testDjikstraGraph();
	}



	private static void testDjikstraGraph() {
		List<Value> valueList = generateRandomValue(10);
		Graph graph = generateDirectedGraph(valueList).orElse(new Graph());
		Node from = (Node) graph.nodeMap.get(valueList.get(0));
//		List<Edge> edges = dijkstra1(from);
//		System.out.println("test End");
	}

	/**
	 * 测试 dfs and bfs graph
	 *
	 * @author ZhangYi
	 */
	private static void testDFSAndBFSGraph() {
		int testTimes = 100000;
		System.out.println("test  Begin...");
		for (int index = 0; index < testTimes; index++) {
			int length = new Random().nextInt(100);
//			System.out.println(String.format("随机长度为 %d", length));
			List<Value> edges = generateRandomValue(length);
			Graph graph = generateDirectedGraph(edges).orElse(new Graph());
			Graph noDirectGraph = generateNoDirectedGraph(edges).orElse(new Graph());

			List<Node> bfsNode1 = bfsGraph(graph);
			List<Node> bfsNode2 = bfsGraph(noDirectGraph);
			if (! validated(bfsNode1, bfsNode2)) {
				System.out.println("Fuck ! bfs test fail");
			}

			List<Node> dfsNode1 = dfsGraph(graph);
			List<Node> dfsNode2 = dfsGraph(noDirectGraph);
			if (! validated(dfsNode1, dfsNode2)) {
				System.out.println("Fuck ! dfs test fail");
			}
		}

		System.out.println("test end...");
	}

	/**
	 * 已验证 两个集合的节点是否一致
	 *
	 * @param bfsNode1 bfs节点1
	 * @param bfsNode2 bfs node2
	 * @return boolean
	 * @author ZhangYi
	 */
	private static boolean validated(List<Node> bfsNode1, List<Node> bfsNode2) {
		if (CollectionUtils.isEmpty(bfsNode1) && CollectionUtils.isEmpty(bfsNode2)) {
			return true;
		}
		Set<String> nodeValueSet = bfsNode2.stream()
				.filter(node -> Objects.nonNull(node))
				.map(node -> String.valueOf(node.value))
				.collect(Collectors.toSet());
		for (Node node : bfsNode1) {
			if (!nodeValueSet.contains(node.value)){
				return false;
			}
		}
		return true;
	}

	/**
	 * DFS 深度优先遍历 图
	 *
	 * @param graph 图
	 * @return {@code List<Node> }
	 * @author ZhangYi
	 */
	private static List<Node> dfsGraph(Graph graph) {
		Stack<Node> stack = new Stack<>();
		Set<Node> visitedNodes = new HashSet<>();

		List<Node> dfsResult = new ArrayList<>();

		for (Object value : graph.nodeMap.values()) {
			Node from = value instanceof Node ? (Node) value : null;

			if (Objects.isNull(from) || visitedNodes.contains(from)) {
				continue;
			}
			stack.push(from);
			// 业务代码, 所有的节点只会 进栈一次
			dfsResult.add(from);
			visitedNodes.add(from);
			while (!stack.isEmpty()){
				Node current = stack.pop();

				for (Object nextNode : current.nextNodes) {
					Node val = (Node) nextNode;
					if (!visitedNodes.contains(val)){
						stack.push(current);
						stack.push(val);
						// 业务代码, 所有的节点只会 进栈一次
						dfsResult.add(val);

						visitedNodes.add(val);
					}
				}
			}
		}


		return dfsResult;
	}

	/**
	 *  BFS 图宽度优先遍历
	 *
	 * @param graph 图
	 * @author ZhangYi
	 */
	private static List<Node> bfsGraph(Graph graph) {
		Queue<Node> queue = new LinkedList<>();
		Set<Node> visitedNodes  = new HashSet<>();
		List<Node> bfsResult = new ArrayList<>();

		if (CollectionUtils.isEmpty(graph.nodeMap)){
			return bfsResult;
		}

		for (Object value : graph.nodeMap.values()) {
			Node from = value instanceof Node ? (Node) value : null;
			// 入队
			if (Objects.isNull(from) || visitedNodes.contains(from)){
				continue;
			}
			// 保证是未访问过的节点,入队
			queue.add(from);
			visitedNodes.add(from);
			while (!queue.isEmpty()){
				Node current = queue.poll();
				// 业务代码,所有的元素都只能出队一次
				bfsResult.add(current);
				for (Object nextNode : current.nextNodes) {
					if (! visitedNodes.contains(nextNode)){
						Node node = (Node) nextNode;
						queue.add(node);
						visitedNodes.add(node);
					}
				}
			}
		}

		return bfsResult;
	}

	/**
	 * 生成无向图
	 *
	 * @param edges 边缘
	 * @return {@code Optional<Graph> }
	 * @author ZhangYi
	 */
	private static Optional<Graph> generateNoDirectedGraph(List<Value> edges) {
		if (CollectionUtils.isEmpty(edges)) {
			return Optional.empty();
		}
		Graph<String> graph = new Graph<String>();
		for (Value edg : edges) {
			int weight = edg.getWeight();
			String from = edg.getFrom();
			String to = edg.getTo();
			if (!graph.nodeMap.containsKey(from)){
				graph.nodeMap.put(from, new Node<>(from));
			}
			if (!graph.nodeMap.containsKey(to)){
				graph.nodeMap.put(to,new Node<>(to));
			}
			Node<String> fromNode = graph.nodeMap.get(from);
			Node<String> toNode = graph.nodeMap.get(to);

			Edge<String> fromEdge = new Edge<>(weight, fromNode, toNode);
			Edge<String> toEdge = new Edge<>(weight, toNode, fromNode);

			/***
			 * 关于出入度
			 * 代码中注释掉了出入度的增加操作（fromNode.out++, toNode.in++ 等），
			 * 因为在无向图中，这些通常是没有意义的。如果 Node 类中包含这些属性，它们应该是相等的，代表节点的度数
			 */
//			fromNode.out++;
//			toNode.in++;
			fromNode.nextNodes.add(toNode);
			fromNode.nextEdges.add(fromEdge);

			toNode.nextNodes.add(fromNode);
			toNode.nextEdges.add(toEdge);
//			toNode.out++;
//			fromNode.in++;
			graph.edgeList.add(fromEdge);
			graph.edgeList.add(toEdge);
		}
		return Optional.of(graph);
	}

	/**
	 * 生成随机值
	 *
	 * @param size 尺寸
	 * @return {@code List<Value> }
	 * @author ZhangYi
	 */
	private static List<Value> generateRandomValue(int size) {
		List<Value> values = new ArrayList<>();

//		List<String> stringList = Arrays.asList("A", "B", "C", "D", "E", "F", "G", "H", "I", "J");
		List<String> stringList = Arrays.asList("A", "B", "C", "D");

		if (size == 0) {
			return values;
		}
		// 已经生成的边的记录
		Set<String> edgeSet = new HashSet<>();
		for (int index = 0; index < size; index++) {
			Random random = new Random();
			String from = stringList.get(random.nextInt(stringList.size()));
			String to = stringList.get(random.nextInt(stringList.size()));
			if (!edgeSet.contains(from + to) || !edgeSet.contains(to + from)) {
				Value value = new Value(random.nextInt(100), from, to);
				values.add(value);
				// 记录
				edgeSet.add(from + to);
				edgeSet.add(to + from);
			}
		}
		return values;
	}

	/**
	 * 生成有向图
	 *
	 * @param edges 边缘
	 * @return {@code Graph }
	 * @author ZhangYi
	 */
	private static Optional<Graph> generateDirectedGraph(List<Value> edges) {
		if (CollectionUtils.isEmpty(edges)) {
			return Optional.empty();
		}
		Graph<String> graph = new Graph<String>();
		for (Value edg : edges) {
			int weight = edg.getWeight();
			String from = edg.getFrom();
			String to = edg.getTo();

			if (!graph.nodeMap.containsKey(from)) {
				graph.nodeMap.put(from, new Node<>(from));
			}
			if (!graph.nodeMap.containsKey(to)) {
				graph.nodeMap.put(to, new Node<>(to));
			}
			Node<String> fromNode = graph.nodeMap.get(from);
			Node<String> toNode = graph.nodeMap.get(to);

			Edge<String> edge = new Edge<>(weight, fromNode, toNode);

			fromNode.out++;
			toNode.in++;
			fromNode.nextNodes.add(toNode);
			fromNode.nextEdges.add(edge);

			graph.edgeList.add(edge);

		}
		return Optional.of(graph);
	}


	/**
	 * dijkstra 最短单源路径, 可以是有向图,也可以是无向图
	 *
	 * @param from 从 出发点, 如果不在 distinceMap 中的节点,则认为无穷远
	 * @return {@code Map<Node, Integer> }
	 * @author ZhangYi
	 */
	private static Map<Node, Integer> dijkstra1(Node from) {
		// Node , 到达下一个节点的距离
		Map<Node, Integer> distinceMap = new HashMap<>();
		Set<Node> lockNodeSet = new HashSet<>();

		// 当前节点,到其自身的距离为0; 不在distinceMap 中的,认为是无穷远的
		distinceMap.put(from,0);


		Node minNode = getMinNodeFromDistinceMapUnLockedNodeSet(distinceMap, lockNodeSet);
		while (minNode != null){
			if (lockNodeSet.contains(minNode)){
				continue;
			}
			Integer nodeDistince = distinceMap.get(minNode);
			for (Object nextEdge : minNode.nextEdges) {
				Edge edge = (Edge) nextEdge;
				Node toNode = edge.to;
				if (!distinceMap.containsKey(toNode)){
					distinceMap.put(toNode,edge.weight+nodeDistince);
				}else {
					distinceMap.put(toNode,Math.min(edge.weight+nodeDistince,distinceMap.get(toNode)));
				}
			}

			lockNodeSet.add(minNode);
			minNode = getMinNodeFromDistinceMapUnLockedNodeSet(distinceMap, lockNodeSet);
		}

		return distinceMap;
	}

	/**
	 * 从距离map 中未锁定节点集获取最小距离节点
	 *
	 * @param distinceMap distince地图
	 * @param lockNodeSet 锁定节点集
	 * @return {@code Node }
	 * @author ZhangYi
	 */
	private static Node getMinNodeFromDistinceMapUnLockedNodeSet(Map<Node, Integer> distinceMap, Set<Node> lockNodeSet) {
		Node minNode = null;
		int minDistince =Integer.MAX_VALUE;

		for (Map.Entry<Node, Integer> entry : distinceMap.entrySet()) {
			Integer nodeDistince = entry.getValue();
			Node node = entry.getKey();
			if (!lockNodeSet.contains(node) && nodeDistince < minDistince){
				minDistince = nodeDistince;
				minNode = node;
			}
		}
		return minNode;
	}

	private static Map<Node, Integer> dijkstra2(Node from) {
		DefinedGraphHeap.MyGraphHeap heap = new DefinedGraphHeap.MyGraphHeap(100);
		heap.addOrUpdateOrIgnore(new DefinedGraphHeap.NodeRecod(0,from));
		Map<Node, Integer> distinceMap = new HashMap<>();
		distinceMap.put(from,0);

		while (!heap.isEmpty()){
			DefinedGraphHeap.NodeRecod recod = heap.pop();
			int distince = recod.getDistince();

			distinceMap.put(recod.getNode(),distince);

			Node node = recod.getNode();
			for (Object nextEdge : node.nextEdges) {
				Edge edge = (Edge) nextEdge;
				heap.addOrUpdateOrIgnore(new DefinedGraphHeap.NodeRecod(distince+edge.weight,edge.to));
			}
		}

		System.out.println(1);
		return distinceMap;
	}
}
